package medium;

/**
 * @Description :给你一个字符串 s，找到 s 中最长的回文子串。
 * @Author : machong
 * @Date : 2022/4/6 1:45
 * @Version : 1.0
 **/
public class leetCode05_longestPalindrome {
    //方法一 ：暴力解法 时间复杂度O(n^3) 空间复杂度O(1)
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            for (int j = i+1; j < len; j++) {
                if(isPalindrome(charArray,i,j) == true && maxLen < j-i+1){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);
    }

    private boolean isPalindrome(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //方法二：中心扩散方法 时间复杂度：O(n^2) 空间复杂度：O(1)
    public String longestPalindrome2(String s) {
        if (s == null || s.length() < 1){
            return "";
        }
        // 初始化最大回文子串的起点和终点
        int start = 0;
        int end   = 0;
        // 遍历每个位置，当做中心位
        for (int i = 0; i < s.length(); i++) {
            // 分别拿到奇数偶数的回文子串长度
            int len_odd = expandCenter(s,i,i);
            int len_even = expandCenter(s,i,i + 1);
            // 对比最大的长度
            int len = Math.max(len_odd,len_even);
            // 计算对应最大回文子串的起点和终点
            if (len > end - start){
                start = i - (len - 1)/2;
                //考虑了子串长度为奇偶的不同情况
                end = i + len/2;
            }
        }
        // 注意：这里的end+1是因为 java自带的左闭右开的原因
        return s.substring(start,end + 1);
    }
    /**
     * @param s             输入的字符串
     * @param left          起始的左边界
     * @param right         起始的右边界
     * @return              回文串的长度
     */
    private int expandCenter(String s,int left,int right){
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        // 跳出循环的时候恰好满足 s.charAt(left) ！= s.charAt(right)
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            --left;
            ++right;
        }
        // 回文串的长度是right-left+1-2 = right - left - 1
        return right - left - 1;
    }
    //方法三：动态规划 TODO
}
